1. Technical Field
The present invention relates to wireless sensor networks and more particularly, to determining placement of nodes within a wireless sensor network.
2. Discussion of Related Art
A Wireless Sensor Network (WSN) comprises spatially distributed autonomous devices, the devices using sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. For example, these networks are currently being used for industrial automation and retail and environmental monitoring. WSNs are typically constructed using small, battery-powered devices, each device including a general purpose processor, a radio transmitter and receiver, memory, and a range of sensors. Crossbow's® mote is an example of such a device.
It is generally acknowledged that the most valuable resource in such devices is battery power, as changing batteries involves a significant amount of human effort, particularly if the devices are located in remote or dangerous locations. The biggest draw on battery power is radio transmission, and protocols which minimize power usage by reducing the amount of transmissions that a given node needs to perform (e.g., through the use of epidemic protocols, by channel reservation, etc.) are regularly being developed.
Current models of radio communication can be extremely complicated, as they are influenced by factors such as the materials that the radio waves pass through, the nature of the surfaces that the radio waves reflect against, and other forms of radio communication occurring nearby. Practically, when a site is being equipped with a WSN, there is a need to test which nodes are capable of communicating with other nodes rather than being able to deduce connectivity from a model of the site. Consequently, significant effort is needed to determine the placement of wireless sensor nodes at an installation site.
The problem of determining the placement of nodes within a WSN can be described as an optimization problem. Cost efficiency suggests that a minimal set of nodes should be used while resiliency of the network suggests that a maximum number of paths should exist within the network. Since these two objectives are contradictory, a compromise is typically made, and a maximum number of nodes (e.g., 1000) and a minimum set of distinct paths between important points in the network (e.g., 3) is selected by a network architect.
Such WSNs are typically organized as trees (or forests) in which the root node connects the sensor network to a fixed network. Within the tree are nodes which gather data, referred to as source nodes, and nodes which simply relay data to the root. All leaf nodes in the tree are source nodes, but not all source nodes are leaf nodes. When determining the placement of nodes within a wireless sensor network, a maximum set of nodes that allows a minimum number of distinct trees to be built is selected, wherein each tree includes every source node. By selecting the nodes in this way, the wireless sensor network can survive failure of a number of nodes less than the minimum number of distinct trees. This is typically achieved through an ad-hoc process of testing settings at the installation site.